package letcode;
import com.sun.org.apache.bcel.internal.generic.NEW;
import org.junit.Test;

import java.sql.Array;
import java.util.*;
//1.求数组动态和
/*
public class Solution {
    public static int[] runningSum(int[] nums) {
        int[] runningSum = new int[nums.length];
        for (int i = 0; i < runningSum.length; i++) {
            for (int j = 0; j <= i; j++) {
                runningSum[i] += nums[j];
            }
        }
        return runningSum;
    }

    public static void main(String[] args)
    {
        System.out.println((Arrays.toString(runningSum(new int[]{1, 2, 3, 4}))));
    }
}
*/


//判断是否为质数并计算次数
// 2.1优化后的暴力求解法
/*public class Solution{
    public static int countPrimes(int n){
        if (n<3)
            return 0;
        int count=1;
        //i+=2是要过滤偶数
        for(int i=3;i<n;i+=2)
        {
        count+=isPrimes(i)?1:0;

        }
        return count;
    }
    //判断是否为素数函数
    public static boolean isPrimes(int i)
    {
        //求算数平方根，减少运算次数。
        int sqrt=(int) Math.sqrt(i);
        //一个素数永远不可能被偶数2整除，步长为2，减少时间复杂度。
        for(int j=3;j<=sqrt;j+=2){
            if(i%j==0)
            {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        System.out.println(isPrimes(20));
        System.out.println(countPrimes(20));
    }
}*/



//2.2埃氏筛的方法计数质数

/*
public class Solution{
    public static int countPrimers(int n ){
        int ans=0;
        int[]isprime=new int[n];
        Arrays.fill(isprime,1);
        System.out.println(isprime);
        for (int j=2;j<n;j++)
        {
           if(isprime[j]==1)
                System.out.println(j);
                ans++;
            for(int i=j;(long)i*j<n;i++)
            {
                isprime[i*j]=0;
            }
        }
        return ans;
    }
    public static void main(String[] args) {
        System.out.println(countPrimers(20));
    }
}*/




//3.同构字符串
/*

public class Solution {
    public static boolean isIsomorphi(String s, String t) {
        HashMap<Object, Object> m1 = new HashMap<>();
        if (s.length()!=t.length()) return false;
        char[] chars = s.toCharArray();
        char[] chart = t.toCharArray();
        for (int i=0;i<chars.length;i++)
        {
            int b=chars[i];
            m1.put(chars[i],b);

        }
        System.out.println(m1);
            return true;
    }

    public static void main(String[] args) {
        System.out.println(isIsomorphi("acc","abc"));
    }
}
*/

/*3.2同构字符串
给定两个字符串s和t，判断它们是否是同构的。
如果s中的字符可以被替换得到t，那么这两个字符串是同构的。
所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身*/

/*
public class Solution{
    public static boolean isIsomorphic(String s,String t)
    {
        char[] chars=s.toCharArray();
        char[] chart=t.toCharArray();
        if (s.length()!=t.length()) return false;
        int len=s.length();
        for (int i=0;i<len;i++)
        {
            if(s.indexOf(chars[i]) !=t.indexOf(chart[i]))
            {
                return false;
            }
          *//*  System.out.print(chars[i]+" "+s.indexOf(chars[i])+" ");
            System.out.println(chart[i]+" "+t.indexOf(chart[i]));*//*
        }
        return true;
    }
    public static void main(String[] args)
    {
        boolean a=isIsomorphic("asdfga","qwertq");
        System.out.println(a);
    }
    }*/


//4.杨辉三角形
//给定一个非负整数 numRows，生成杨辉三角的前 numRows 行
/*

class Solution {
    public static List<List<Integer>>generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for (int i = 0; i < numRows; ++i) {
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <=i; ++j) {
                if (j == 0 || j == 1) {
                    row.add(1);
                } else {
                    row.add(ret.get(i-1).get(j-1) + ret.get(i-1).get(j));
                }
            }
         ret.add(row);
        }
        return ret;
    }
    public static void main(String[] args) {
        for(int i=0;i<9;i++)
        {;
            for(int j=0;j<i;j++)
            {
                System.out.println(generate(5));
            }
        }
    }
}

*/

/**
 * 从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
 */

class Solution {
    public int lastRemaining(int n, int m) {

        return f(n, m);
    }

    public int f(int n, int m) {
        if (n == 1) {
            return 0;
        }
        int x = f(n - 1, m);
        return (m + x) % n;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.lastRemaining(5,3));
    }

}






